//一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出
//这个数字。 
//
// 
//
// 示例 1: 
//
// 输入: [0,1,3]
//输出: 2
// 
//
// 示例 2: 
//
// 输入: [0,1,2,3,4,5,6,7,9]
//输出: 8 
//
// 
//
// 限制： 
//
// 1 <= 数组长度 <= 10000 
// Related Topics 数组 二分查找 
// 👍 87 👎 0

package leetcode.editor.cn;
//Java：0～n-1中缺失的数字
public class QueShiDeShuZiLcof{
    public static void main(String[] args) {
        Solution solution = new QueShiDeShuZiLcof().new Solution();
        
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int missingNumber(int[] nums) {
        //使用二分法进行查找
        int i = 0,j = nums.length -1;
        while ( i <= j ){
            int m = (i + j) /2 ;
            //左
            if ( m == nums[m] ){
                i = m + 1;
            }
            //右
            else {
                j = m - 1;
            }
        }
        //返回一个比比较的位置多1的元素，代表的是当前缺失的元素
        return i;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
